/*
 * @lc app=leetcode.cn id=390 lang=typescript
 *
 * [390] 消除游戏
 */

// @lc code=start
function lastRemaining(n: number): number {
  let ans = 1;
  // 扫描的次数
  let k = 0;
  // 等差数列的步进
  let step = 1;
  // 元素的数量
  let count = n;

  while (count > 1) {
    if (k % 2 === 0) {
      //正向扫描
      ans += step;
    } else {
      // 反向扫描
      ans = count % 2 === 0 ? ans : ans + step;
    }
    k++;
    step = step << 1;
    count = count >> 1;
  }

  return ans;
}
// @lc code=end
